package org.fle4y.app.server.database;

import java.sql.SQLException;

/**
 * author : xiehui<br>
 * company : northking <br>
 * Create at: 2012-6-26<br>
 * 
 * @version : 1.0<br>
 * mailto:flexie@foxmail.com<br>
 * Description :
 */
public class Index {
	private String sName;
	private int iFields;
	private int iColumn[];
	private int iType[];
	private boolean bUnique;
	private Node root;
	private int iColumn_0, iType_0;
	private static int iNeedCleanUp;

	Index(String name, int column[], int type[], boolean unique) {
		sName = name;
		iFields = column.length;
		iColumn = column;
		iType = type;
		bUnique = unique;
		iColumn_0 = iColumn[0];
		iType_0 = iType[0];
	}
	
	Node getRoot() {
		return root;
	}

	void setRoot(Node r) {
		root = r;
	}

	String getName() {
		return sName;
	}

	boolean isUnique() {
		return bUnique;
	}

	int[] getColumns() {
		return iColumn;
	}

	void insert(Node i) throws SQLException {
		Object data[] = i.getData();
		Node n = root, x = n;
		boolean way = true;
		int compare = -1;

		while (true) {
			if (n == null) {
				if (x == null) {
					root = i;
					return;
				}
				set(x, way, i);
				break;
			}

			x = n;
			compare = compareRow(data, x.getData());
			way = compare < 0;
			n = child(x, way);
		}
		while (true) {
			int sign = way ? 1 : -1;
			switch (x.getBalance() * sign) {
			case 1:
				x.setBalance(0);
				return;
			case 0:
				x.setBalance(-sign);
				break;
			case -1:
				Node l = child(x, way);
				if (l.getBalance() == -sign) {
					replace(x, l);
					set(x, way, child(l, !way));
					set(l, !way, x);
					x.setBalance(0);
					l.setBalance(0);
				} else {
					Node r = child(l, !way);
					replace(x, r);
					set(l, !way, child(r, way));
					set(r, way, l);
					set(x, way, child(r, !way));
					set(r, !way, x);
					int rb = r.getBalance();

					x.setBalance((rb == -sign) ? sign : 0);
					l.setBalance((rb == sign) ? -sign : 0);
					r.setBalance(0);
				}
				return;
			}

			if (x.equals(root)) {
				return;
			}

			way = from(x);
			x = x.getParent();
		}
	}
	void delete(Object row[], boolean datatoo) throws SQLException {
		Node x = search(row);
		if (x == null) {
			return;
		}
		Node n;

		if (x.getLeft() == null) {
			n = x.getRight();
		} else if (x.getRight() == null) {
			n = x.getLeft();
		} else {
			Node d = x;
			x = x.getLeft();
			while (x.getRight() != null) {
	
				x = x.getRight();
			}

			n = x.getLeft();
			int b = x.getBalance();

			x.setBalance(d.getBalance());
			d.setBalance(b);
			Node xp = x.getParent();
			Node dp = d.getParent();

			if (d == root) {
				root = x;
			}
			x.setParent(dp);

			if (dp != null) {
				if (dp.getRight().equals(d)) {
					dp.setRight(x);
				} else {
					dp.setLeft(x);
				}
			}
			if (xp == d) {
				d.setParent(x);

				if (d.getLeft().equals(x)) {
					x.setLeft(d);
					x.setRight(d.getRight());
				} else {
					x.setRight(d);
					x.setLeft(d.getLeft());
				}
			} else {
				d.setParent(xp);
				xp.setRight(d);
				x.setRight(d.getRight());
				x.setLeft(d.getLeft());
			}
			x.getRight().setParent(x);
			x.getLeft().setParent(x);
			d.setLeft(n);
			if (n != null) {
				n.setParent(d);
			}
			d.setRight(null);

			x = d;
		}

		boolean way = from(x);

		replace(x, n);

		n = x.getParent();

		x.delete();

		if (datatoo) {
			x.rData.delete();
		}

		while (n != null) {
			x = n;
			int sign = way ? 1 : -1;
			switch (x.getBalance() * sign) {

			case -1:
				x.setBalance(0);

				break;

			case 0:
				x.setBalance(sign);

				return;

			case 1:
				Node r = child(x, !way);
				int b = r.getBalance();

				if (b * sign >= 0) {
					replace(x, r);
					set(x, !way, child(r, way));
					set(r, way, x);

					if (b == 0) {
						x.setBalance(sign);
						r.setBalance(-sign);

						return;
					}

					x.setBalance(0);
					r.setBalance(0);

					x = r;
				} else {
					Node l = child(r, way);

					replace(x, l);

					b = l.getBalance();

					set(r, way, child(l, !way));
					set(l, !way, r);
					set(x, !way, child(l, way));
					set(l, way, x);
					x.setBalance((b == sign) ? -sign : 0);
					r.setBalance((b == -sign) ? sign : 0);
					l.setBalance(0);

					x = l;
				}
			}

			way = from(x);
			n = x.getParent();
		}
	}
	Node find(Object data[]) throws SQLException {
		Node x = root, n;
		while (x != null) {
			int i = compareRowNonUnique(data, x.getData());
			if (i == 0) {
				return x;
			} else if (i > 0) {
				n = x.getRight();
			} else {
				n = x.getLeft();
			}

			if (n == null) {
				return null;
			}

			x = n;
		}

		return null;
	}
	Node findFirst(Object value, int compare) throws SQLException {
		Node x = root;
		int  iTest = 1;

		if (compare == Expression.BIGGER) {
		    iTest = 0;
		}
		while (x != null) {
		    boolean t = compareValue(value, x.getData()[iColumn_0]) >= iTest;

		    if (t) {
			Node r = x.getRight();

			if (r == null) {
			    break;
			}

			x = r;
		    } else {
			Node l = x.getLeft();

			if (l == null) {
			    break;
			}

			x = l;
		    }
		}

		while (x != null
		       && compareValue(value, x.getData()[iColumn_0]) >= iTest) {
		    x = next(x);
		}

		return x;
	    }

	Node first() throws SQLException {
		Node x = root, l = x;
		while (l != null) {
			x = l;
			l = x.getLeft();
		}

		return x;
	}
	Node next(Node x) throws SQLException {
		if ((++iNeedCleanUp & 127) == 0) {
			x.rData.cleanUpCache();
		}

		Node r = x.getRight();

		if (r != null) {
			x = r;
			Node l = x.getLeft();
			while (l != null) {
				x = l;
				l = x.getLeft();
			}

			return x;
		}

		Node ch = x;

		x = x.getParent();

		while (x != null && ch.equals(x.getRight())) {
			ch = x;
			x = x.getParent();
		}

		return x;
	}
	private Node child(Node x, boolean w) throws SQLException {
		return w ? x.getLeft() : x.getRight();
	}

	private void replace(Node x, Node n) throws SQLException {
		if (x.equals(root)) {
			root = n;

			if (n != null) {
				n.setParent(null);
			}
		} else {
			set(x.getParent(), from(x), n);
		}
	}
	
	private void set(Node x, boolean w, Node n) throws SQLException {
		if (w) {
			x.setLeft(n);
		} else {
			x.setRight(n);
		}

		if (n != null) {
			n.setParent(x);
		}
	}

	private boolean from(Node x) throws SQLException {
		if (x.equals(root)) {
		    return true;
		}
		return x.equals(x.getParent().getLeft());
	    }
	private Node search(Object d[]) throws SQLException {
		Node x = root;

		while (x != null) {
			int c = compareRow(d, x.getData());

			if (c == 0) {
				return x;
			} else if (c < 0) {
				x = x.getLeft();
			} else {
				x = x.getRight();
			}
		}

		return null;
	}
	private int compareRowNonUnique(Object a[], Object b[]) throws SQLException {
		int i = Column.compare(a[iColumn_0], b[iColumn_0], iType_0);

		if (i != 0) {
			return i;
		}

		for (int j = 1; j < iFields - (bUnique ? 0 : 1); j++) {
			i = Column.compare(a[iColumn[j]], b[iColumn[j]], iType[j]);

			if (i != 0) {
				return i;
			}
		}

		return 0;
	}

	private int compareRow(Object a[], Object b[]) throws SQLException {
		int i = Column.compare(a[iColumn_0], b[iColumn_0], iType_0);

		if (i != 0) {
			return i;
		}

		for (int j = 1; j < iFields; j++) {
			i = Column.compare(a[iColumn[j]], b[iColumn[j]], iType[j]);

			if (i != 0) {
				return i;
			}
		}

		return 0;
	}

	private int compareValue(Object a, Object b) throws SQLException {
		return Column.compare(a, b, iType_0);
	}

}
